\section{Parallelizing for the GPU}
\label{sec:parallel}

We modified the serial binning approach so that it would work in CUDA on a GPU.  (This code can be found in \texttt{binned.cu}.)  For additional reference, we used a naive parallel CUDA implementation.  This is given in the appendix.

To implement binning on the CPU, we used two additional structures in addition to the array of particles: an array of bins and an array of bin sizes.  The bin array stores bins, which in turn contain the indices of the particles in that bin.  The bin sizes array stores the sizes of each bin.  This was necessary because we could not use the \texttt{C++ STL vector} class; more on this in Section~\ref{sec:disc}.

Our code first creates the three structures (particles, bins, and bin sizes) on the CPU and then copies them to the GPU device using \texttt{cudaMemcpy}.  We then call \texttt{cudaThreadSynchronize} before beginning the simulation in order to synchronize across threads and again at the end of the simulation.

The high-level steps of our implementation are the same as in the serial case.  The difference is that now, the handling of bins and the particles within them are divided up among the GPU threads in order to exploit data parallelism.  In order to do this, we index the bin and bin sizes arrays with the thread ID.  Bin filling is parallelized by assigning each thread a particle based on its thread ID; each thread then calculates the bin number, stores the thread ID, and increments the bin size.  This can cause a race condition; we discuss this further in Section~\ref{sec:disc}.

The results from our parallel binned implementation are compared with the results from the naive binned implementation in Figure~\ref{fig:money}.  We observe that the binning procedure takes longer than the actual calculation for simulations with less than 2500 particles; this can be seen in the graph and causes the scaling to appear nonlinear until after approximately 10000 particles, at which point it is clearly linear.

\begin{figure}[h!]
\begin{center}
\includegraphics[width=.75\textwidth]{./figs/money_plot.pdf}
\caption{A comparison of our parallel binning approach with the naive parallel approach.  Our approach scales linearly with particle size once the number of particles becomes greater than approximately 10000, greatly outpacing the naive approach.}
\end{center}
\label{fig:money}
\end{figure}
